package 动态规划.背包问题;

/**
 * Copyright (C) 2023 思创数码科技股份有限公司
 * <p/>
 * 版权所有
 * <p/>
 * 类名　　  : 背包01
 * 功能概要  :
 *
 * @author yangwk
 * @date 2024/5/5 17:01
 */
public class 背包01 {
    public static void main(String[]   args) {
        int[]  price= {4, 5, 10, 11,13};
        int[] weight = {3, 4, 7, 8, 9};
        int totalWeight = 17;
        System.out.println(maxProfit(weight, price, totalWeight));
//        System.out.println(maxProfit1(weight, price, totalWeight));
    }

    public static int maxProfit(int[] weight, int[] price, int totalWeight) {
        int[][] dp = new int[weight.length + 1][totalWeight + 1];
        for (int i = 1; i <= weight.length; i++) {
            for (int w = 1; w <= totalWeight; w++) {
                if (weight[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i - 1][w], price[i-1] + dp[i-1][w - weight[i - 1]]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        int x[] = new int[weight.length];
        int w = totalWeight;
        for (int i = weight.length-1; i > 1; i--) {
            if (dp[i][w] == dp[i - 1][w]) {
                x[i] = 0;
            }else{
                x[i] = 1;
                w = w - weight[i-1];
                System.out.print("[" + weight[i] +"-"+ price[i] + "]" + "\t");
            }
        }
        return dp[weight.length][totalWeight];
    }
    public static int maxProfit1(int[] weight, int[] price, int totalWeight) {
        int[] dp = new int[totalWeight + 1];
        dp[0] = 0;

        for (int i = 0; i < weight.length; i++) { //遍历物品
            for (int j = totalWeight; j >= 0; j--) {   //遍历背包容量
                if (weight[i] > j) continue;
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + price[i]);
            }
        }
        return dp[totalWeight];
    }
}
